package algorithm.dynamic_programming;

import java.util.*;

public class Coffee {


    public static class Machine{
        public int timePoint;
        public int workTime;

        public Machine(int timePoint, int workTime) {
            this.timePoint = timePoint;
            this.workTime = workTime;
        }
    }

    public static Integer[] minTimeOfDrinking(int[] arr, int n){
        PriorityQueue<Machine> queue = new PriorityQueue<>(new Comparator<Machine>() {
            @Override
            public int compare(Machine o1, Machine o2) {
                return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
            }
        });
        for (int i = 0; i < arr.length; i++) {
            queue.add(new Machine(0, arr[i]));
        }
        Integer[] drinks = new Integer[n];
        for (int i = 0; i < n; i++) {
            Machine machine = queue.poll();
            machine.timePoint += machine.workTime;
            drinks[i] = machine.timePoint;
            queue.add(machine);
        }
        return drinks;
    }


    //要根据题目的要求定义好递归过程的意义
    public static int minTime(int[] drinks, int a, int b, int index, int washLine){
        if(index == drinks.length - 1){
            if(drinks[index] >= washLine)
                return drinks[index] + a;
            else
                return Math.min(washLine + a, drinks[index] + b);
        }

        int washTime = drinks[index] > washLine ? minTime(drinks, a, b, index + 1, drinks[index] + a) :
                                                  minTime(drinks, a, b, index + 1, washLine + a);
        int p1 = Math.max(washTime, Math.max(drinks[index], washLine) + a);

        int dry = minTime(drinks, a, b, index + 1, washLine);
        int p2 = Math.max(dry, drinks[index] + b);

        return Math.min(p1, p2);
    }


    public static int minTime2(int[] drinks, int a, int b){
        int washTime = 0;
        for (int i = 0; i < drinks.length; i++) {
            washTime = Math.max(washTime, drinks[i]);
            washTime += a;
        }
        int[][] dp = new int[drinks.length][washTime + 1];
        for (int i = 0; i < washTime + 1; i++) {
            if(drinks[drinks.length - 1] >= i)
                dp[drinks.length - 1][i] = drinks[drinks.length - 1] + a;
            else
                dp[drinks.length - 1][i] = Math.min(i + a, drinks[drinks.length - 1] + b);
        }
        for (int i = drinks.length - 2; i >=0 ; i--) {
            for (int j = 0; j < washTime + 1 - a; j++) {
                int time1 = drinks[i] > j ? dp[i + 1][drinks[i] + a] : dp[i + 1][j + a];
                int p1 = Math.max(time1, Math.max(drinks[i], j) + a);

                int dry = dp[i + 1][j];
                int p2 = Math.max(dry, drinks[i] + b);

                dp[i][j] = Math.min(p1, p2);
            }
        }
        return dp[0][0];
    }


    public static void main(String[] args) {
//        int[] test = {1, 1, 5, 5, 7, 10, 12, 12, 12, 12, 12, 12, 15};
//        int a1 = 3;
//        int b1 = 10;
//        System.out.println(minTime2(test, a1, b1));

        Integer[] drinking = minTimeOfDrinking(new int[]{1, 3, 7}, 10);
        List<Integer> list = Arrays.asList(drinking);
        System.out.println(list);
    }
}
